package gold.digger;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC525 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int findMaxLength(int[] arr) {
            if (null == arr || arr.length <= 0) return 0;
            Map<Integer, Integer> map = new HashMap<>();
            map.put(0, -1);//map记录sum出现的位置,0初始位置为-1，即无数值累加和的时候，最左侧端点
            int preSum = 0, maxLen = 0;

            for (int i = 0; i < arr.length; i++) {
                if (arr[i] == 0) preSum += -1;
                else preSum += 1;

                if (map.containsKey(preSum))
                    maxLen = Math.max(maxLen, i - map.get(preSum));//当前前缀和和之前前缀和之间差值为0，也就是此中间区间为0
                else map.put(preSum, i);
            }

            return maxLen;
        }
    }

    public void run() {
        Solution solution = new Solution();
        int[] arr = {0, 1, 0, 1};
        System.out.println(solution.findMaxLength(arr));
    }

    public static void main(String[] args) throws Exception {
        LC525 an = new LC525();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
